// =====================================================================================
// 
//       Filename:  routes.h
// 
//    Description:  Description d'un réseau routier et procédures d'importation depuis
//    				les formats MID/MIF
// 
//        Version:  1.0
//        Created:  24/06/2009 21:18:10
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:  
// 
// =====================================================================================

#ifndef  ROUTES_INC
#define  ROUTES_INC

#include	<string>
#include	<vector>
#include	<list>
#include	<deque>
#include	<fstream>
#include	"parser.h"
#include	"erreurs.h"
#include	"config.h"
#include	"kdtree.h"
#include	"geometrie.h"
#include	"graphe.h"
#include	"attributs.h"
#include	"gisobjects.h"

using namespace std;

/**
 * \class Intersection
 * \brief Intersection de deux routes
 *
 * La classe est la représentation logique d'un noeud du réseau routier, situé à l'intersection entre deux tronçons. Elle sert de base au calcul d'itinéraire. Elle contient les attributs géographiques du sommet (coordonnées) et peut contenir ses attributs physiques s'ils sont disponibles.
 */
class Intersection:public Sommet,public Point {
	public:
		int tag;	//!< Valeur supplémentaire, réservée pour certains besoins, notamment dans l'association du sommet à une source

		/**
		 * \brief Constructeur standard d'une intersection à partir de ses caractéristiques
		 *
		 * Le constructeur construit la variable d'intersection à partir de toutes ses caractéristiques.
		 * \param pid Identifiant de l'intersection, utilisé pour le calcul d'itinéraire
		 * \param pnom Nom de l'intersection
		 * \param px Abscisse géographique de l'intersection, nulle par défaut
		 * \param py Ordonnée géographique de l'intersection, nulle par défaut
		 */
		Intersection(int pid,const string pnom,double px=0,double py=0):Sommet(pid,pnom),Point(px,py) {}
};

/**
 * \fn bool true_condition_i(const Intersection *p)
 * \brief Fonction de condition qui retourne toujours vrai
 *
 * La fonction est utilisée pour la définition d'une condition par défaut que doit vérifier un point lors de la recherche du plus proche voisin. Cette condition particulière retourne toujours vrai, ce qui permet de recherche le plus proche voisin parmi tous les points du réseau sans exception. Elle est utilisée comme paramètre par défaut de la fonction membre Kd_tree::neighbour()
 * \param p Point pour lequel la condition est vérifiée, mais il n'est pas utilisé dans cette fonction particulière et ne sert qu'à assurer la concordance du type de la fonction avec le type attendu
 * \return Toujours true
 */
bool true_condition_i(const Intersection *p);

/**
 * \fn void coordonnees(const void* point,double* coords)
 * \brief Fonction qui encapsule la fonction membre de la classe Point de même nom permettant l'extraction des coordonnées de l'instance.
 *
 * La fonction retourne dans le tableau coords les coordonnées du point mentionné par son premier argument. Aucune vérification de dépassement n'est faite et la taille du tableau fourni doit correspondre au nombre de coordonnées attendues. Cette fonction est utilisée pour la construction des arbres de recherche du plus proche voisin.
 * \param point Pointeur anonyme vers une variable de type Point dont les coordonnées doivent être extraites
 * \param coords Tableau qui recevra les coordonnées du point. Il doit être créé avant l'appel à la fonction.
 */
void coordonnees(const void* point,double* coords);

/**
 * \fn void carre_distance(const void *point,const double *ppoint)
 * \brief Fonction qui encapsule la fonction membre de la classe Point de même nom permettant le calcul du carré de la distance de l'instance à un autre point.
 *
 * La fonction retourne le carré de la distance entre les deux points passés en argument. Cette fonction est utilisée pour la construction des arbres de recherche du plus proche voisin.
 * \param point Pointeur anonyme vers une variable de type Point
 * \param ppoint Pointeur anonyme vers une seconde variable tableau avec les coordonnées du point de référence
 * \return Carré de la distance entre les deux points passés en argument
 */
double carre_distance(const void *point,const double *ppoint);

class Reseau;

/**
 * \class Troncon
 * \brief Tronçon de route
 *
 * La classe est la représentation logique d'un tronçon de route, portion située entre deux croisements, et qui sert de base au calcul d'itinéraire. Elle contient les attributs physiques (numéro, nom de route, topographie...) et géographiques (description géométrique, position).
 */
class Troncon:public Arc,public Lineique {
	public:
		Reseau *parent;	//!< Réseau auquel appartient le tronçon
		int tag;	//!< Valeur supplémentaire, utilisée pour indiquer si l'arc fait partie d'un itinéraire et qu'il doit être représenté d'une couleur particulière.
		double vitesse;	//!< Vitesse moyenne de circulation sur le tronçon de route

		Troncon(Reseau *pparent,const DescriptionTable *pdescription):Lineique(pdescription),parent(pparent),tag(0),vitesse(1.0) {}	//!< Constructeur standard
		virtual void affiche(ostream& out) const;	//!< Affichage sur le flux de sortie out

		/**
		 * \brief Lecture d'un tronçon de route à partir de fichiers au format MID/MIF (MapInfo)
		 *
		 * La méthode lit un tronçon de route à partir d'un fichier MIF et du fichier MID correspondant. On suppose que ces fichiers contiennent un ensemble d'arcs routiers, représentés par des lignes ou des polylignes.
		 * En revanche, aucune hypothèse n'est réalisée sur le type et le nombre des attributs qui peuvent être quelconques, bien que leur nature doive être indiquée au préalable dans la variable Enregistrement::description.
		 * Les descripteurs géographiques lus dans le fichier MIF sont enregistrés dans la variable PolyLigne, tandis que les attributs lus dans le fichier MID sont stockés dans la structure Enregistrement::data de la classe parente.
		 * Si les données ne peuvent pas être lues, la procédure soulève une exception de type IOException. Si la fin du fichier est atteinte, la fonction retourne la valeur false. Si la ligne a bien pu être lue, la fonction renvoie true.
		 * \param mif Descripteur de flux d'entrée correspondant au fichier MIF. Celui-ci doit être au préalable ouvert et prêt pour la lecture de données.
		 * \param mid Descripteur de flux d'entrée correspondant au fichier MID. Celui-ci doit être au préalable ouvert et prêt pour la lecture de données.
		 * \param sep Séparateur des données dans le fichier MID, par défaut égal à ','.
		 * \return true si la lecture s'est bien passée, false si aucune donnée n'a pu être lue (fin de fichier)
		 */
		bool lecture(ifstream &mif,ifstream &mid,char sep=',') throw (IOException,ParseException);

		/**
		 * \brief Calcul du poids de l'arc
		 *
		 * La méthode calcule le poids de l'arc, qui sera utilisé pour le calcul d'itinéraire. Par défaut, ce poids correspond à la longueur de l'arc divisée par la vitesse de parcours unitaire. Si un arbre syntaxique est donné en argument, il sera utilisé pour le calcul du poids de l'arc qui sera alors le résultat de l'évaluation de l'expression représentée par l'arbre syntaxique. Elle peut être modifiée, par exemple dans une classe descendante, pour calculer le poids selon d'autres paramètres.
		 * \param arbre Arbre syntaxique utilisé pour le calcul du poids
		 */
		virtual double calcule_poids(AST::SyntaxNode *arbre=0) const;
};

/**
 * \fn ostream& operator<< (ostream& out,const Troncon &t);
 * \brief Affiche les principaux renseignements sur le tronçon sur un flux de sortie
 *
 * La fonction affiche l'identifiant et les numéros des sommets initial et final du tronçon t sur le flux de sortie out, puis retourne ce même flux de sortie.
 * \param out Flux de sortie sur lequel afficher le tronçon
 * \param t Tronçon à afficher
 * \return Flux de sortie non modifié
 */
ostream& operator<< (ostream& out,const Troncon &t);

/**
 * \class Reseau
 * \brief Ensemble de tronçons de routes (classe Troncon)
 *
 * Un réseau est un ensemble de tronçons de routes. Il hérite de la classe Graphe, et inclut à la fois des données cartographiques et des données de description de réseaux. C'est la classe de base sur laquelle sont effectués les calculs d'itinéraires.
 */
class Reseau:public Graphe {
	/**
	 * \fn friend ostream& operator<< (ostream &out,const Reseau &r)
	 * \brief Affiche les principales données du réseau sur un flux de sortie
	 *
	 * La fonction affiche les principaux renseignements sur le réseau (frontières du domaine, nombre de sommets...) r sur le flux de sortie spécifié par out.
	 * \param out Flux de sortie sur lequel afficher le réseau
	 * \param r Réseau à afficher
	 * \return Flux de sortie non modifié
	 */
	friend ostream& operator<< (ostream &out, const Reseau &r);
	friend class Zone;
	public:
		double xmin;	//!< Abscisse minimale du réseau routier
		double xmax;	//!< Abscisse maximale du réseau routier
		double ymin;	//!< Ordonnée minimale du réseau routier
		double ymax;	//!< Ordonnée maximale du réseau routier
		DescriptionTable *description;	//!< Description de la table des attributs du réseau routier

		Reseau():description(0),arbre(0) {}	//!< Constructeur standard
		~Reseau();	//!< Destructeur standard, libère les ressources associées

		/**
		 * \brief Retourne la liste des intersections
		 *
		 * La seule utilité de cette fonction est de retourner un nouveau tableau contenant la liste des intersections avec le type Intersection au lieu du type Sommet hérité de la classe Graphe. Cette conversion des types du conteneur n'est cependant pas possible automatiquement, même s'il s'agit d'un type hérité.
		 * \return Tableau des intersections du réseau
		 */
		vector<Intersection*> intersections() const;

		/**
		 * \brief Recherche d'un élément par dichotomie dans le tableau des intersections
		 *
		 * La fonction suppose que la liste est triée par ordre croissant des positions, où la relation d'ordre sur l'espace des positions est définie de la façon suivante.
		 * Soient deux points \f$P_1(x_1,y_1)\f$ et \f$P_2(x_2,y_2)\f$, la relation d'ordre totale sur l'espace des points est définie par :
		 * \f$ P_1\leq P_2 \Leftrightarrow \left\{\begin{array}{l} x_1\leq x_2 \\ \hbox{si }x_1=x_2\hbox{,}y_1\leq y_2 \\ \end{array}\right.\f$
		 * et
		 * \f$ P_1=P_2 P_2 \Leftrightarrow \left\{\begin{array}{l} x_1=x_2 \\ y_1=y_2 \\ \end{array}\right.\f$
		 * L'élément correspondant au point p est recherché par dichotomie dans le tableau, avec une complexité en \f$ O(n\log n)\f$.
		 * \param p Coordonnées du point à rechercher
		 * \return Intersection correspondant au point p, 0 si l'intersection n'est pas trouvée
		 */
		Intersection* cherchep(const Point &p) const;

		/**
		 * \brief Recherche du sommet du réseau le plus proche d'un point donné
		 *
		 * La méthode recherche le sommet du réseau le plus proche du point dont les coordonnées sont indiquées et retourne la distance de ce point au sommet trouvé.
		 * Elle parcourt systématiquement l'ensemble des points et de ce fait s'exécute en temps O(n).
		 * \param x Abscisse du point
		 * \param y Ordonnée du point
		 * \param noeud Intersection la plus proche du point donné
		 * \param condition Condition que doit vérifier le point trouvé
		 * \return Distance de l'intersection au point indiqué
		 */
		double projection_simple(double x,double y,Intersection *&noeud,bool (*condition)(const Intersection*)=true_condition_i) const;
		
		/**
		 * \brief Recherche du sommet du réseau le plus proche d'un point donné en utilisant l'arbre de recherche
		 *
		 * La méthode recherche le sommet du réseau le plus proche du point dont les coordonnées sont indiquées et retourne la distance de ce point au sommet trouvé.
		 * Elle crée pour ce faire un arbre de recherche (si celui-ci n'existe pas déjà) puis parcourt cette arbre de façon intelligente.
		 * \param x Abscisse du point
		 * \param y Ordonnée du point
		 * \param noeud Intersection la plus proche du point donné
		 * \param condition Condition que doit vérifier le point trouvé
		 * \return Distance de l'intersection au point indiqué
		 */
		double projection(double x,double y,Intersection *&noeud,bool (*condition)(const Intersection*)=true_condition_i);

		/**
		 * \brief Réinitialise les couleurs des sommets et des arcs
		 *
		 * La fonction réinitialise les couleurs de tous les sommets et de tous les arcs, et permet d'effacer un itinéraire passé si celui-ci existe.
		 */
		void init_couleurs();

		/**
		 * \brief Lecture du réseau routier à partir de fichiers MID/MIF
		 *
		 * La méthode lit le contenu de deux fichiers MID et MIF et les charge dans la classe.
		 * \param mif Nom du fichier MIF à lire
		 * \param mid Nom du fichier MID à lire
		 * \param conf Pointeur vers la structure qui contient les paramètres de configuration qui seront mis à jour (index du champ contenant le sens de circulation, index du champ qui contient l'altitude des tronçons de route)
		 */
		void importe_mid_mif(const string &mif,const string &mid,Config &conf);

		Kd_tree<2,Intersection,coordonnees,carre_distance> *arbre;	//!< Arbre de recherche, utilisé pour le repérage rapide de la projection d'un point sur le réseau
};

/**
 * \fn ostream& operator<< (ostream &out,const Reseau &r)
 * \brief Affiche les principales données du réseau sur un flux de sortie
 *
 * La fonction affiche les principaux renseignements sur le réseau (frontières du domaine, nombre de sommets...) r sur le flux de sortie spécifié par out.
 * \param out Flux de sortie sur lequel afficher le réseau
 * \param r Réseau à afficher
 * \return Flux de sortie non modifié
 */
ostream& operator<< (ostream &out, const Reseau &r);

#endif   // ----- #ifndef ROUTES_INC  -----
